package backtracking;

/**
 * @Author: LDeng
 * @Date: 2021-04-15 8:59
 */
public class Queens2 {
    public static void main(String[] args) {

//        int n=125;//1111101
//        System.out.println(Integer.toBinaryString(n));
        new Queens2().placeQueens(12);
    }

    //使用boolean数组标记该列是否有皇后
    boolean[] cols;
    //标记着某一对角线是否有皇后的了（左上->右下）
    boolean[] leftTop;
    //右上->左下
    boolean[] rightTop;

    int[] queens;

    int ways;//多少种摆法

    void placeQueens(int n) {
        if (n < 1) return;
        queens=new int[n];
        cols = new boolean[n];
        leftTop=new boolean[2*n-1];
        rightTop=new boolean[2*n-1];
        place(0);
        System.out.println(n + " 皇后共有 " + ways + " 种摆法 ");
    }

    //从第row行开始摆放皇后
    void place(int row) {
        if (row == cols.length) {//进到这里表示找到一种方法，
            // 走到最后一行还能向下一行找就表示成功了
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            //第col列已经有皇后
            if (cols[col]) continue;
            int ltIndex=row-col+cols.length-1;//row-col+7
            if(leftTop[ltIndex]) continue;//斜线上已经有皇后
            int rtIndex=row+col;
            if(rightTop[rtIndex]) continue;//斜线上已经有皇后

            //能摆放皇后，标记所在的列和斜线为true
            queens[row]=col;
            cols[col]=true;
            leftTop[ltIndex]=true;
            rightTop[rtIndex]=true;
            place(row+1);
            //还原
            cols[col]=false;
            leftTop[ltIndex]=false;
            rightTop[rtIndex]=false;
        }
    }



    //判断第row行 第col列是否可以摆放皇后


    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("========================");
    }

}





